#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
//这是一个对于有向图的Dijkstra算法，保证源点到每一点可达。
#define INF 0x7f7f7f7f;
int n;
int m;
int start_v;
int map[10001][10001];
bool vi[10001];
int dis[10001];

void Dijkstra(int v){
    int lowcost[n] = {};
    dis[v] = 0;
    cout<<"111>>"<<dis[0]<<endl;
    vi[v] = 1;
    for(int i=0;i<n;++i)
        lowcost[i] = map[v][i];
    
    for(int t=0;t<n;++t){
        int min_value = INF;
        int min_index = v;
        for(int i=0;i<n;++i){
            if(vi[i] != 1 && lowcost[i] < min_value){
                min_value = lowcost[i];
                min_index = i;
            }
        }
        cout<<"222>>"<<dis[0]<<endl;
        vi[min_index] = 1;
        dis[min_index] = min_value;
 
        //更新lowcost
        for(int i=0;i<n;++i){
            if(vi[i] == 1) continue;
            cout<<"333>>"<<dis[0]<<endl;
            lowcost[i] = min(lowcost[i], map[min_index][i] + dis[min_index]);
        }
    }

}

int main(){
    cin >> n >> m >> start_v;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            map[i][j] = INF;
    for(int i=0;i<m;++i){
        int x,y;
        cin >> x >> y;
        cin >> map[x-1][y-1];
    }
        cout<<"********"<<endl;

        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                cout<<setw(10)<<map[i][j]<<" ";
            }
            cout<<endl;
        }

    Dijkstra(start_v-1);

/*     for(int i=0;i<n;++i){
        cout<<dis[i]<<" ";
    } */
    return 0;
}